package com.cb2.algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/min-stack/">最小栈(Min Stack)</a>
 * <p>设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。</p>
 * <p>
 * 实现 MinStack 类:
 * <ul>
 *     <li>MinStack() 初始化堆栈对象。</li>
 *     <li>void push(int val) 将元素val推入堆栈。</li>
 *     <li>void pop() 删除堆栈顶部的元素。</li>
 *     <li>int top() 获取堆栈顶部的元素。</li>
 *     <li>int getMin() 获取堆栈中的最小元素。</li>
 * </ul>
 * </p>
 * <p>
 *     <b>示例：</b>
 *     <pre>
 * 示例 1：
 *      输入：
 *          ["MinStack","push","push","push","getMin","pop","top","getMin"]
 *          [[],[-2],[0],[-3],[],[],[],[]]
 *      输出：
 *          [null,null,null,null,-3,null,0,-2]
 *      解释：
 *          MinStack minStack = new MinStack();
 *          minStack.push(-2);
 *          minStack.push(0);
 *          minStack.push(-3);
 *          minStack.getMin();   --> 返回 -3.
 *          minStack.pop();
 *          minStack.top();      --> 返回 0.
 *          minStack.getMin();   --> 返回 -2.
 *     </pre>
 * </p>
 * <p>
 *     <b>提示：</b>
 *     <ul>
 *         <li>-2^31 <= val <= 2^31 - 1</li>
 *         <li>pop、top 和 getMin 操作总是在 非空栈 上调用</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/12 10:25
 */
public class LC0155MinStack_M {
    static class MinStack {
        Deque<Integer> numStack;
        Deque<Integer> minStack;

        public MinStack() {
            numStack = new LinkedList<>();
            minStack = new LinkedList<>();
        }

        public void push(int val) {
            numStack.push(val);
            if (minStack.isEmpty()) {
                minStack.push(val);
            } else {
                minStack.push(Math.min(minStack.peek(), val));
            }
        }

        public void pop() {
            numStack.pop();
            minStack.pop();
        }

        public int top() {
            return numStack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
    }
}